<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    397. Integer Replacement
   </h1>
   <p>
    Given a positive integer
    <i>
     n
    </i>
    and you can do operations as follow:
   </p>
   <p>
   </p>
   <ol>
    <li>
     If
     <i>
      n
     </i>
     is even, replace
     <i>
      n
     </i>
     with
     <code>
      <i>
       n
      </i>
      /2
     </code>
     .
    </li>
    <li>
     If
     <i>
      n
     </i>
     is odd, you can replace
     <i>
      n
     </i>
     with either
     <code>
      <i>
       n
      </i>
      + 1
     </code>
     or
     <code>
      <i>
       n
      </i>
      - 1
     </code>
     .
    </li>
   </ol>
   <p>
    What is the minimum number of replacements needed for
    <i>
     n
    </i>
    to become 1?
   </p>
   <p>
    <b>
     Example 1:
    </b>
   </p>
   <pre>
<b>Input:</b>
8

<b>Output:</b>
3

<b>Explanation:</b>
8 -&gt; 4 -&gt; 2 -&gt; 1
</pre>
   <p>
    <b>
     Example 2:
    </b>
   </p>
   <pre>
<b>Input:</b>
7

<b>Output:</b>
4

<b>Explanation:</b>
7 -&gt; 8 -&gt; 4 -&gt; 2 -&gt; 1
or
7 -&gt; 6 -&gt; 3 -&gt; 2 -&gt; 1
</pre>
  </div>
  <div>
   <h1 class="question_title">
    397. 整数替换
   </h1>
   <p>
    给定一个正整数&nbsp;
    <em>
     n
    </em>
    ，你可以做如下操作：
   </p>
   <p>
    1. 如果&nbsp;
    <em>
     n&nbsp;
    </em>
    是偶数，则用&nbsp;
    <code>
     n / 2
    </code>
    替换&nbsp;
    <em>
     n
    </em>
    。
    <br>
    2. 如果&nbsp;
    <em>
     n&nbsp;
    </em>
    是奇数，则可以用&nbsp;
    <code>
     n + 1
    </code>
    或
    <code>
     n - 1
    </code>
    替换&nbsp;
    <em>
     n
    </em>
    。
    <br>
    <em>
     n&nbsp;
    </em>
    变为 1 所需的最小替换次数是多少？
   </p>
   <p>
    <strong>
     示例 1:
    </strong>
   </p>
   <pre>
<strong>输入:</strong>
8

<strong>输出:</strong>
3

<strong>解释:</strong>
8 -&gt; 4 -&gt; 2 -&gt; 1
</pre>
   <p>
    <strong>
     示例 2:
    </strong>
   </p>
   <pre>
<strong>输入:</strong>
7

<strong>输出:</strong>
4

<strong>解释:</strong>
7 -&gt; 8 -&gt; 4 -&gt; 2 -&gt; 1
或
7 -&gt; 6 -&gt; 3 -&gt; 2 -&gt; 1
</pre>
  </div>
 </body>
</html>